using System.Diagnostics;
using System.Collections.Generic;

//
// * Copyright (c) 2002-2009 "Neo Technology,"
// *     Network Engine for Objects in Lund AB [http://neotechnology.com]
// *
// * This file is part of Neo4j.
// * 
// * Neo4j is free software: you can redistribute it and/or modify
// * it under the terms of the GNU Affero General Public License as
// * published by the Free Software Foundation, either version 3 of the
// * License, or (at your option) any later version.
// * 
// * This program is distributed in the hope that it will be useful,
// * but WITHOUT ANY WARRANTY; without even the implied warranty of
// * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// * GNU Affero General Public License for more details.
// * 
// * You should have received a copy of the GNU Affero General Public License
// * along with this program. If not, see <http://www.gnu.org/licenses/>.
// 
namespace org.neo4j.kernel.impl.util
{


	public class IntArray
	{
		private int[] rels;
		private int arrayCount = 0;

		public IntArray()
		{
			rels = new int[2];
		}

		public IntArray(int initialCapacity)
		{
			rels = new int[initialCapacity];
		}

		public IntArray(int[] array)
		{
			rels = array;
			arrayCount = array.Length;
		}

		public virtual void Add(int id)
		{
			if (arrayCount == rels.Length)
			{
				int[] newRels = new int[rels.Length * 2];
				System.Array.Copy(rels, 0, newRels, 0, rels.Length);
				rels = newRels;
			}
			rels[arrayCount++] = id;
		}

		public virtual void AddAll(IntArray array)
		{
			if (array == null)
			{
				return;
			}
			if (array.Length() + arrayCount > rels.Length)
			{
				int newSize = rels.Length * 2;
                while (array.Length() + arrayCount > newSize)
				{
					newSize = newSize * 2;
				}
				int[] newRels = new int[newSize];
				System.Array.Copy(rels, 0, newRels, 0, arrayCount);
				rels = newRels;
			}
            System.Array.Copy(array.GetArray(), 0, rels, arrayCount, array.Length());
            arrayCount += array.Length();
		}

		public virtual int Length()
		{
			return arrayCount;
		}

		public virtual int[] GetArray()
		{
			return rels;
		}

		public virtual int Get(int i)
		{
			Debug.Assert(i >= 0 && i < arrayCount);
			return rels[i];
		}

		public static IntArray ComposeNew(IntArray src, IntArray add, IntArray remove)
		{
			if (remove == null)
			{
				if (src == null)
				{
					return add;
				}
				if (add != null)
				{
                    IntArray newArray = new IntArray(add.Length() + src.Length());
					newArray.AddAll(src);
					newArray.AddAll(add);
					return newArray;
				}
				return src;
			}
			else
			{
				if (src == null && add == null)
				{
					return null;
				}
				int newLength = 0;
				if (add != null)
				{
                    newLength += add.Length();
				}
				if (src != null)
				{
                    newLength += src.Length();
				}
				IntArray newArray = new IntArray(newLength);
                //HashSet<int> @set = new HashSet<int>(remove.Length + 1, 1.0f);
                List<int> @set = new List<int>(remove.Length() + 1);
                for (int i = 0; i < remove.Length(); i++)
				{
					@set.Add(remove.Get(i));
				}
				newArray.AddAll(src);
                for (int i = 0; i < newArray.Length(); i++)
				{
					int @value = newArray.Get(i);
					if (@set.Contains(@value))
					{
						bool swapSuccessful = false;
                        for (int j = newArray.Length() - 1; j >= i + 1; j--)
						{
							int backValue = newArray.Get(j);
							newArray.arrayCount--;
							if (!@set.Contains(backValue))
							{
								newArray.GetArray()[i] = backValue;
								swapSuccessful = true;
								break;
							}
						}
						if (!swapSuccessful) // all elements from pos in remove
						{
							newArray.arrayCount--;
						}
					}
				}
				if (add != null)
				{
                    for (int i = 0; i < add.Length(); i++)
					{
						int @value = add.Get(i);
						if (!@set.Contains(@value))
						{
							newArray.Add(@value);
						}
					}
				}
			   return newArray;
			}
		}

//    public static IntArray composeNew( IntArray src, IntArray add, 
//        IntArray remove )
//    {
//        if ( remove == null )
//        {
//            if ( src == null )
//            {
//                return add;
//            }
//            if ( add != null )
//            {
//                IntArray newArray = new IntArray( add.length() + src.length() );
//                newArray.addAll( src );
//                newArray.addAll( add );
//                return newArray;
//            }
//            return src;
//        }
//        else
//        {
//            if ( src == null )
//            {
//                return null;
//            }
//            // TODO: merge add and remove array then append add array to result
//            int[] newArray = new int[src.length()];
//            int[] srcArray = src.getArray();
//            int[] removeArray = remove.getArray();
//            assert removeArray.length <= srcArray.length;
//            System.arraycopy( srcArray, 0, newArray, 0, src.length() );
//            Arrays.sort( newArray );
//            Arrays.sort( removeArray );
//            int newArraySize = newArray.length;
//            int startSearchFrom = 0;
//            int checkTo = removeArray.length; // can decrease if we swap
//            for ( int i = 0; i < checkTo; i++ )
//            {
//                int index = binarySearch( newArray, startSearchFrom, 
//                    newArraySize, removeArray[i] );
//                if ( index >= 0 )
//                {
//                    // next search can start from here
//                    startSearchFrom = index + 1;
//                    
//                    // find element we can swap with
//                    for ( int j = newArraySize - 1; j >= startSearchFrom; j-- )
//                    {
//                        int swapValue = newArray[j];
//                        int rIndex = binarySearch( removeArray, i, checkTo, 
//                            swapValue );
//
//                        newArraySize--;
//                        
//                        // ok last element in newArray == 
//                        // last element in removeArray
//                        if ( rIndex > 0 ) 
//                        {
//                            checkTo--;
//                            // continue with second last to see if that is 
//                            // swapable
//                        }
//                        else // we swap with this element
//                        {
//                            newArray[index] = newArray[j];
//                            break;
//                        }
//                    }
//                }
//            }
//            IntArray newIntArray = new IntArray( newArray );
//            newIntArray.arrayCount = newArraySize;
//            return newIntArray;
//        }
//    }
//    
//    private static int binarySearch( int[] array, int startOffset, 
//        int endOffset, int value )
//    {
//        int pIndex = startOffset + ( endOffset - startOffset ) / 2;
//
//        int valueFound = array[pIndex];
//        if ( valueFound == value )
//        {
//            return pIndex;
//        }
//        if ( pIndex == startOffset ) // search exhausted
//        {
//            return -1;
//        }
//        
//        if ( value < valueFound )
//        {
//            return binarySearch( array, startOffset, pIndex, value );
//        }
//        else
//        {
//            return binarySearch( array, pIndex, endOffset, value );
//        }
//    }
	}
}